1. Field of the Invention
The present invention generally relates to the global Internet, and more particularly to Internet routing protocols for supporting multicast packet delivery.
2. Description of the Related Art
The Internet is the world""s largest network, and it has become essential to businesses as well as to consumers. The success of Internet is partly due to the simplicity of routing protocols used in the network for packet delivery.
There are basically three types of packets delivery mechanisms including xe2x80x9cunicastxe2x80x9d that allows the delivery of information from a source to a particular destination, xe2x80x9cbroadcastxe2x80x9d that allows the delivery of information from a source to every destination in the network, and xe2x80x9cmulticastxe2x80x9d that allows the delivery of information from a source to a selected group of destinations in the network.
Today, in the Internet, the multicast is supported by using routers called xe2x80x9cClass Dxe2x80x9d routers. In this scheme, prior to conducting the multicast, necessary resources are reserved at those involved Class D routers. Then, multicast may be started. At the conclusion of the multicast, such reserved resources must be freed so that they become available for other multicasts.
Because of this reservation and resource allocation involvement, this Class D router-based multicast scheme is suitable for supporting relatively long lasting multicasts (e.g., minutes instead of seconds to minimize the overhead of reservation) that involve large numbers of destinations.
However, because of this reservation and resource allocation involvement, it is not suitable for supporting a large numbers of small group multicasts, due to reservation time and resource consumption at each Class D router to keep track of the state of each multicast.
Moreover, because each Class D router must create entries for each multicast group and this entry occupies a certain space, only a finite number of multicasts can be supported.
A way to support an extremely large number of small multicast groups is to let each packet carry routing destinations and alleviate routers from keeping track of states of individual multicast.
There are basically two distinctive methods to carry destinations for multicast purposes. A first method carries a list of multicast destinations and indicates that the packet is a multicast packet (e.g., namely indicating that a packet is not a unicast packet).
A second method is to carry multicast routing information (e.g., sometimes referred to as xe2x80x9csource routingxe2x80x9d or xe2x80x9crouting treexe2x80x9d) that includes the multicast destinations and indicates that the packet is a multicast packet.
The second approach has many drawbacks. For example, a source node must create a proper routing sub-tree that contains multicast destinations that is computation intensive, a routing tree description becomes a substantial overhead of each multicast packet, and a new multicast-enabled router must perform a fairly complex routing sub-trees regeneration process for every multicast packet received.
Therefore, desirable solutions for small group multicast are based on a multicast packet that carries a list of multicast destinations and simply indicates that the packet is a multicast packet delivery (e.g., this indicator allows a new multicast router to differentiate multicast packets easily from unicast packets).
In this approach, there are two distinctive Internet Protocol (IP) packet formats for small group multicast depending on how the IP destination address field is used for multicasting packets. Both formats have a control field bit (MC) indicating whether or not a given packet is a multicast (MC=1) or unicast (MC=0).
One type of multicast packet format is to place one of the multicast destination IP addresses into the IP packet destination field and the remainder of multicast destination IP addresses in the OPTIONS field of the IP packet.
Another type of multicast packet format is to choose a multicast-capable router (e.g., the router that supports the new multicast routing protocol) in the network and place its IP address into the IP packet destination field, and place all of the multicast destination IP addresses in the OPTIONS field. Each of these two formats offers a completely different implementation of routing algorithms and each gives pros and cons. The present invention, as described in detail below, claims an innovative multicast routing solution when the latter multicast packet format has been used (e.g., choosing a multicast capable router and placing an IP address into the IP packet destination field and placing all of the multicast destination IP addresses in the OPTIONS field).
In view of the foregoing and other problems of the conventional methods and structures, an object of the present invention is to provide a method and structure in which a multicast scheme and method are realized that are suitable for simultaneously supporting a very large number of small group multicasts.
Another object of the present invention is to support gradual introduction of the new multicast-capable router(s) into the network without introducing any disruptions to on-going operations.
Yet another object of the present invention is to introduce a scheme where the introduction of a single multicast-capable router will enable the entire network multicast-capable.
A further object of the present invention is to guarantee the optimum multicast routing (e.g., each packet will be delivered from a multicast-capable router to every destination along the shortest path defined in the exiting unicast routing).
Another object of the present invention is to provide a scheme that improves resource utilization and multicast efficiency as the number of multicast-capable routers are introduced into the network and as the existing unicast routers are upgraded to the new multicast-capable routers.
A still further object of the present invention is to utilize the existing unicast routing protocols for determining multicasting routes.
Another object of the present invention is to impose no new functional requirement at each multicast destination node by guaranteeing that each destination always receives unicast packets.
Yet another object of the present invention is to allow simple swapping of the existing unicast routing protocol software with the new multicast-capable routing protocol software.
In a first aspect of the present invention, a routing table for use with a router in a world-wide network, includes extending an existing routing table to include a xe2x80x9cmulticast-destinationxe2x80x9d (MD) column.
In a second aspect, a routing system, includes a routing unit for updating a next-node (NN) column of a routing table and for routing unicast packets by referencing the NN column of the routing table, a packet regeneration unit for referencing a column MD of the routing table and for selectively creating copies of at least one of unicast and multicast packets, and a multicast-destination (MD) discovery unit for updating the MD column of the routing table.
In a third aspect, a method of processing a packet, includes receiving a packet at a router, checking by the router if the packet""s destination is itself or not, if the packet""s destination is not the router, then the said packet is routed in a traditional manner, and if the received packet""s destination is itself and if an entry in a routing table is MC=1 indicating that the packet is a multicast packet, then forwarding the packet to a packet regeneration process.
The present invention, as described in detail below, claims an innovative multicast routing solution when the latter multicast packet format has been used (e.g., choosing a multicast capable router and placing IP address into the IP packet destination field and placing all of the multicast destination IP addresses in the OPTIONS field). The Internet IP packet which support this latter multicast packet format may appear as the following: in addition to other fields of the Internet IP packet, it has a PROTOCOL field indicating that the packet is a small group multicast, the Source IP Address representing the source of the multicast packet, the Destination IP Address representing the address of one of the small group multicast capable routers in the network, and the OPTIONS field. The OPTIONS field contains CODE indicating small group multicast, contains LENGTH indicating the total number of bytes for multicast destinations (equivalent to the number of destinations), contains POINTER indicating the start position of multicast destinations, and followed by the IP addresses of the small group multicast destinations.
With the unique and unobvious aspects of the invention, an unlimited number of xe2x80x9csmallxe2x80x9d multicasts can be supported. For purposes of the present application, xe2x80x9csmallxe2x80x9d is preferably a number of the group being less than ten (10), but of course the number depends on the designer""s constraints and requirements. A small group is preferable since each packet must carry the destinations that belong to the multicast group. Hence, if there are ten (10) people in the distribution list, then a first packet must carry nine destination addresses. Similarly, if there are 20 people, then the first packet must carry 19 addresses. The smaller the group size, the smaller the packet overhead becomes. Hence, the present invention is especially advantageous, for example, when a few people (e.g., a small group) are to have a conference, conduct messaging etc., over the Internet or another similar network.
Therefore, in the present invention, each multicast packet (indicated by MC=1) carries multicast destinations in the OPTIONS field, and its IP destination address is set to one of a plurality of multicast-capable routers in the network.
Another key advantage of the invention is that a conventional routing table is taken and modified. That is, the invention extends the conventional routing table to include a multicast capable router destination information. Hence, the invention is not building a new table, but is simply modifying an existing table in a unique and unobvious way.
Yet another key advantage of the invention is that the new multicast capable routers can coexist with the conventional routers or any number of conventional routers"" routing software can be upgraded to the new multicast capable routing software.
Still another key advantage of the invention is that no performance penalty is imposed on the conventional unicast routing.